package cxydmmszl.chapter09.t175;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 在两个排序数组中找到第 k 小的数
 * <li style="color: green;">Desc</li>
 * 给定两个有序数组 arr1 和 arr2，再给定一个整数 K，返回所有数中第 K 小的数。
 * <br/><br/>[要求]<br/>
 * 如果 arr1 的长度为 N，arr2 的长度为 M，
 * 时间复杂度请达到 O(log(minN,M))，额外空间复杂度O(1)。
 * <br/><br/>备注：<br/>
 * 1⩽N⩽10^5<br/>
 * 0⩽arr1[i], arr2[i]⩽10^9
 * <li style="color: green;">Input</li>
 * 第一行三个整数 N, M, K 分别表示数组 arr1, arr2 的大小，以及 K。
 * 接下来一行 N 个整数，表示 arr1 内的元素。
 * 再接下来一行 M 个整数，表示 arr2 内的元素。
 * <li style="color: green;">Output</li>
 * 输出一个整数表示答案
 * <li style="color: blue;">Link</li> CD82
 *
 * @author habitplus
 * @since 2021-10-11 15:09
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int m = nextInt();
        int k = nextInt();
        int[] arr1 = new int[n];
        int[] arr2 = new int[m];

        for (int i = 0; i < n; i++) {
            arr1[i] = nextInt();
        }

        for (int i = 0; i < m; i++) {
            arr2[i] = nextInt();
        }

        int ans = getUpMedian(arr1, arr2, k);
        System.out.println(ans);
    }

    private static int getUpMedian(int[] arr1, int[] arr2, int k) {
        if (arr1 == null || arr2 == null
                || k < 1
                || k > arr1.length + arr2.length) {
            throw new RuntimeException("Argument is invalid!");
        }

        int[] longs = arr1.length >= arr2.length ? arr1 : arr2;
        int[] shorts = arr1.length > arr2.length ? arr2 : arr1;
        int lenL = longs.length;
        int lenS = shorts.length;

        if (k <= lenS) {
            return getUpMedian(shorts, 0, k - 1, longs, 0, k - 1);
        }

        if (k > lenL) {
            if (shorts[k - lenL - 1] >= longs[lenL - 1]) {
                return shorts[k - lenL - 1];
            }
            if (longs[k - lenS - 1] >= shorts[lenS - 1]) {
                return longs[k - lenS - 1];
            }
            return getUpMedian(shorts, k - lenL, lenS - 1, longs, k - lenS, lenL - 1);
        }

        if (longs[k - lenS - 1] >= shorts[lenS - 1]) {
            return longs[k - lenS - 1];
        }

        return getUpMedian(shorts, 0, lenS - 1, longs, k - lenS, k - 1);
    }

    /*
        在两个长度相等的有序数组中，寻找上中位数
     */
    private static int getUpMedian(int[] arr1, int l1, int r1, int[] arr2, int l2, int r2) {
        int mid1, mid2, offset;
        while (l1 < r1) {
            mid1 = (l1 + r1) / 2;
            mid2 = (l2 + r2) / 2;

            offset = ((r1 - l1 + 1) & 1) ^ 1;
            if (arr1[mid1] > arr2[mid2]) {
                // 排除 arr1 的【右半部分】，arr2 的【左半部分】
                r1 = mid1;
                l2 = mid2 + offset;
            } else if (arr1[mid1] < arr2[mid2]) {
                // 排除 arr1 的【左半部分】，arr2 的【右半部分】
                r2 = mid2;
                l1 = mid1 + offset;
            } else {
                return arr1[mid1];
            }
        }

        return Math.min(arr1[l1], arr2[l2]);
    }
}
